package com.leetcode.problems;


import java.util.*;

import static java.lang.Math.max;

/**leetcode
 * Created by gongenbo on 2017/6/26.
 */
public class Solution {
    public static void main(String[] args){
        Solution su=new Solution();
        /*
        System.out.println(su.reverseString("hello"));
        System.out.println(su.hammingDistance(2,9));
        int[] nums={1,4,2,9,44,22};
        System.out.println(su.arrayPairSum(nums));*/
        //System.out.println(su.lengthOfLongestSubstring("pwwkew"));
        //String[] strs={"flower","flow","flight"};
        //System.out.println(strs[1].substring(2,3));
        //System.out.println(su.longestCommonPrefix(strs));
        /*
        String s1 = "ab";
        String s2 = "eidbaooo";
        System.out.println(su.checkInclusion(s1,s2));
        System.out.println(su.multiply("123","123"));
        String s1="the sky is blue";
        System.out.println(su.reverseWords(s1));
        List<String> list=Arrays.asList("/home/gongenbo/y".split("/"));
        System.out.println(list.size());
        System.out.println(su.simplifyPath("/home/"));
        System.out.println(su.restoreIpAddresses("25525511135"));
        int[] arr1 = {-1, 0, 1, 2, -1, -4};
        System.out.println(su.threeSum(arr1));
        int[][] ss={{0,0,1,0,0,0,0,1,0,0,0,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},{0,1,1,0,1,0,0,0,0,0,0,0,0},{0,1,0,0,1,1,0,0,1,0,1,0,0},{0,1,0,0,1,1,0,0,1,1,1,0,0},{0,0,0,0,0,0,0,0,0,0,1,0,0},{0,0,0,0,0,0,0,1,1,1,0,0,0},{0,0,0,0,0,0,0,1,1,0,0,0,0}};
        int[][] ss={{0,0,0,0,0,0,0,0}};
        int[][] ss={{1,1,0,0,0},{1,1,0,0,0},{0,0,0,1,1},{0,0,0,1,1}};
        System.out.println(su.maxAreaOfIsland(ss));
        int[] nums = {4,5,6,7,0,1,2};
        int target = 0;
        int[] nums = {4,5,6,7,0,1,2};
        int target = 3;
        int[] nums={1};
        int target=1;
        System.out.println(su.search(nums,target));
        //int[] nums={1,3,5,4,7};
        //int[] nums={2,2,2,2,2};
        int[] nums={1,3,5,7};
        System.out.println(su.findLengthOfLCIS(nums));
        int[] nums={3,2,3,1,2,4,5,5,6};
        int k=4;
        System.out.println(su.findKthLargest(nums,k));
        //int[] nums={100, 4, 200, 1, 3, 2};
        int[] nums={1,2,0,1};
        System.out.println(su.longestConsecutive(nums));*/
        System.out.println(su.getPermutation(3,3));
    }
    /**
     * 344. Reverse String
     * Example:
     * Given s = "hello", return "olleh".
     * @param s
     * @return
     */
    public String reverseString(String s) {
        if(s.length()<=1){
            return s;
        }
        StringBuffer sbf=new StringBuffer();
        for(int i=s.length()-1;i>=0;i--){
            sbf.append(s.charAt(i));
        }
        return sbf.toString();
    }

    /**
     * 461  汉明距离
     * @param x
     * @param y
     * @return
     */
    public int hammingDistance(int x, int y) {
        String result=Integer.toBinaryString(x^y);
        int diff=0;
        for(int i=0;i<result.length();i++){
            if(result.charAt(i)=='1'){
                diff++;
            }
        }
        return diff;
    }

    /**
     * 617. Merge Two Binary Trees
     * @param t1
     * @param t2
     * @return
     */
    public TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
        if(t1==null&&t2==null){
            return null;
        }else if(t1==null&&t2!=null){
            return t2;
        }else if(t1!=null&&t2==null){
            return t1;
        }else{
            t1.val+=t2.val;
            t1.left=mergeTrees(t1.left,t2.left);
            t1.right=mergeTrees(t1.right,t2.right);
        }
        return t1;
    }
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
     }

    /**
     * 561. Array Partition I
     * @param nums
     * @return
     */
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum=0;
        for(int m=0;m<nums.length-1;m+=2){
            sum+=nums[m];
        }
        return sum;
    }
    /**
     * bytedance 1.1.无重复字符的最长子串
     */
    public int lengthOfLongestSubstring_bak(String s) {
        if(s.length()<=0)
            return 0;
        //选择每一趟最大的
        String max="";
        for(int i=0;i<s.length();i++){
            StringBuffer sub=new StringBuffer();
            int flag=1;
            for(int j=i;j<s.length();j++){
                sub.append(s.substring(j,j+1));
                if(j+2>s.length())
                    break;
                //检查是否有重复
                for(int m=0;m<sub.length();m++){
                    //System.out.println("sub:"+sub+"    m:"+sub.substring(m,m+1)+"  sj:"+s.substring(j+1,j+2));
                    if(sub.substring(m,m+1).equals(s.substring(j+1,j+2))){
                        flag=0;
                        break;
                    }
                }
                if(flag==0)
                    break;
            }
            if(sub.length()>max.length())
                max=sub.toString();
        }
        //System.out.println("max:"+max);
        return max.length();
    }
    /**
     * bytedance 1.1.无重复字符的最长子串
     */
    public int lengthOfLongestSubstring(String s) {
        int[] demo=new int[500];
        int i=0,j=0,max=0;
        while(i<s.length()&&j<s.length()){
            if(demo[s.charAt(j)]==0){
                demo[s.charAt(j)]++;
                System.out.println("if j:"+j+" i:"+i+" max:"+max+" demo "+s.charAt(j)+":"+demo[s.charAt(j)]);
                j++;
                max=(j-i)>max?(j-i):max;
            }else{
                demo[s.charAt(j)]=0;
                max=(j-i)>max?(j-i):max;
                System.out.println("else j:"+j+" i:"+i+" max:"+max+" demo "+s.charAt(j)+":"+demo[s.charAt(j)]);
                for(int k=i;k<j;k++){
                    demo[s.charAt(k)]=0;
                    if(s.charAt(k)==s.charAt(j)){
                        i=k;
                        break;
                    }
                }
                i++;
            }
        }
        return max;
    }
    /**
     * bytedance 1.2.最长公共前缀
     */
    public String longestCommonPrefix_bak(String[] strs) {
        if(strs.length<=0)
            return "";
        if(strs.length==1)
            return strs[0];
        StringBuilder sb=new StringBuilder();
        int flag=0;
        //获取最小字段长度
        int minLen=strs[0].length();
        for(int m=0;m<strs.length;m++){
            if(strs[m].length()<minLen)
                minLen=strs[m].length();
        }
        System.out.println("minlen:"+minLen);
        //第几个字段
        for(int i=0;i<minLen;i++){
            //第几个字符串
            for(int j=0;j<strs.length-1;j++){
                //System.out.println("第"+j+"个字符串"+",第"+i+"个字段，是"+strs[j].substring(i,i+1));
                //System.out.println("第"+(j+1)+"个字符串"+",第"+i+"个字段，是"+strs[j+1].substring(i,i+1));
                //System.out.println("sb:"+sb.toString());
                if(strs[j].substring(i,i+1).equals(strs[j+1].substring(i,i+1))){
                    if(j==strs.length-2)
                        sb.append(strs[j].substring(i,i+1));
                }else{
                    flag=1;
                    break;
                }
            }
            if(flag==1)
                break;
        }
        return sb.toString();
    }
    /**
     * bytedance 1.2.最长公共前缀
     */
    public String longestCommonPrefix(String[] strs) {
        StringBuilder result = new StringBuilder();

        if (strs!= null && strs.length > 0){

            Arrays.sort(strs);

            char [] a = strs[0].toCharArray();
            char [] b = strs[strs.length-1].toCharArray();

            for (int i = 0; i < a.length; i ++){
                if (b.length > i && b[i] == a[i]){
                    result.append(b[i]);
                }
                else {
                    return result.toString();
                }
            }
        }
            return result.toString();
    }
    /**
     * bytedance 1.3.字符串的排列 from https://blog.csdn.net/qq_26410101/article/details/81042615
     */
    public boolean checkInclusion(String s1, String s2) {
        if(s1.length()>s2.length()) return false;
        HashMap<Character,Integer> memo1=new HashMap<Character,Integer>();
        HashMap<Character,Integer> memo2=new HashMap<Character,Integer>();
        for(Character k='a';k<='z';k++){
            memo1.put(k,0);
            memo2.put(k,0);
        }
        for(int i=0;i<s1.length();i++){
            memo1.put(s1.charAt(i),memo1.get(s1.charAt(i))+1);
        }
        for(int j=0;j<s2.length();j++){
            if(j<s1.length()){
                memo2.put(s2.charAt(j),memo2.get(s2.charAt(j))+1);
            }else{
                memo2.put(s2.charAt(j),memo2.get(s2.charAt(j))+1);
                memo2.put(s2.charAt(j-s1.length()),(memo2.get(s2.charAt(j-s1.length()))-1));
            }
            if(memo1.equals(memo2))
                return true;
        }
        return false;
    }
    /**
     * bytedance 1.4.字符串相乘
     * https://blog.csdn.net/smartnijun/article/details/81739994
     */
    public String multiply(String num1, String num2) {
        if (num1.equals("0") || num2.equals("0"))
            return "0";

        StringBuilder sb = new StringBuilder();
        int a = num1.length();
        int b = num2.length();
        int[] nums = new int[a + b - 2 + 1];

        for (int i = 0 ; i < a ; i ++) {
            for (int j = 0 ; j < b ; j ++) {
                // 按位相乘并保存到 i + j 处
                nums[i + j] += Integer.valueOf(num1.charAt(i) - '0') * Integer.valueOf(num2.charAt(j) - '0');
            }
        }

        // 进位处理，将结果转换成字符串表示
        int carry = 0;
        for (int i = nums.length - 1 ; i >= 0 ; i --) {
            int tmp = nums[i] + carry;
            sb.append(tmp % 10);
            carry = tmp / 10;
        }
        // 处理最高位的进位
        while (carry > 0) {
            sb.append(carry % 10);
            carry = carry / 10;
        }
        // 反转字符串
        return sb.reverse().toString();
    }
    /**
     * bytedance 1.5.翻转字符串里的单词
     */
    public String reverseWords(String s) {
       String[] words=s.trim().split(" +");
       Collections.reverse(Arrays.asList(words));
       return String.join(" ",words);
    }
    /**
     * bytedance 1.6.简化路径
     */
    public String simplifyPath(String path) {
        String[] patchs=path.split("/+");
        LinkedList<String> list=new LinkedList<>();
        for(int i=0;i<patchs.length;i++){
            if(patchs[i].equals("")||patchs[i].equals("."))
                continue;
            if(patchs[i].equals("..")){
                if(list.size()>=1){
                    list.remove(list.size()-1);
                }
                continue;
            }
            list.add(patchs[i]);

        }
        return "/"+String.join("/",list);
    }
    /**
     * bytedance 1.7.复原IP地址
     * https://www.cnblogs.com/grandyang/p/4305572.html
     */
    public List<String> restoreIpAddresses2(String s) {
        List<String> res = new ArrayList<String>();
        //n是段数，
        helper(s, 0, "", res);
        return res;
    }
    /**
     * bytedance 1.7.复原IP地址解法2非递归
     * https://www.cnblogs.com/grandyang/p/4305572.html
     */
    public List<String> restoreIpAddresses(String s) {
        List<String> res = new ArrayList<String>();
        for (int a = 1; a < 4; ++a)
            for (int b = 1; b < 4; ++b)
                for (int c = 1; c < 4; ++c)
                    for (int d = 1; d < 4; ++d)
                        if (a + b + c + d == s.length()) {
                            int A = Integer.parseInt(s.substring(0, a));
                            int B = Integer.parseInt(s.substring(a, a + b));
                            int C = Integer.parseInt(s.substring(a + b, a + b + c));
                            int D = Integer.parseInt(s.substring(a + b + c));
                            if (A <= 255 && B <= 255 && C <= 255 && D <= 255) {
                                String t = String.valueOf(A) + "." + String.valueOf(B) + "." + String.valueOf(C) + "." + String.valueOf(D);
                                //防止出现01这种
                                if (t.length() == s.length() + 3) res.add(t);
                            }
                        }
        return res;
    }
    public void helper(String s, int n, String out, List<String> res) {
        if (n == 4) {
            if (s.isEmpty()) res.add(out);
            return;
        }
        //对于每一段，我们分别用一位，两位，三位来尝试
        for (int k = 1; k < 4; ++k) {
            if (s.length() < k) break;
            int val = Integer.parseInt(s.substring(0, k));
            if (val > 255 || k != String.valueOf(val).length()) continue;
            //最后一个不加点
            helper(s.substring(k), n + 1, out + s.substring(0, k) + (n == 3 ? "" : "."), res);
        }
    }
    /**
     * bytedance 2.1. 3数之和
     */
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            //第一个只能小于等于0
            if (nums[i] > 0) break;
            //去重
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int j = nums.length - 1;
            int target = 0 - nums[i];
            int k = i + 1;
            while (k < j) {
                if (nums[k] + nums[j] == target) {
                    List<Integer> item = Arrays.asList(nums[i], nums[k], nums[j]);
                    result.add(item);
                    while (k < j && nums[k] == nums[k + 1]) k++;
                    while (k < j && nums[j] == nums[j - 1]) j--;
                    k++;j--;
                } else if (nums[k] + nums[j] < target) {
                    k++;
                } else {
                    j--;
                }
            }
        }
        return result;
    }
    public List<List<Integer>> threeSum_bak(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        for(int a=0;a<=nums.length-3;a++){
            if(a-1>0&&nums[a]==nums[a-1])
                continue;
            for(int b=a+1;b<=nums.length-2;b++){
                if(a-1>0&&nums[a]==nums[a-1])
                    continue;
                for(int c=b+1;c<=nums.length-1;c++){
                    if(a-1>0&&nums[a]==nums[a-1])
                        continue;
                    System.out.println("a:"+a+" b:"+b+" c:"+c);
                    if(nums[a]+nums[b]+nums[c]==0)
                        res.add(Arrays.asList(nums[a], nums[b], nums[c]));
                }
            }
        }
        return res;
    }
    /**
     * bytedance 2.2. 岛屿的最大面积
     */
    public int maxAreaOfIsland(int[][] grid) {
        int mx = 0, n, m;
        n = grid.length;
        m = grid[0].length;
        for(int i=0; i<n; i++)
            for(int j=0; j<m; j++)
            {
                if(grid[i][j] == 1)
                    mx = Math.max(dfs(grid,i,j), mx);
            }
        return mx;
    }
    //图的深度优先搜索遍历算法
    int dfs(int[][] grid, int x0, int y0){
        int n, m, sum=1;
        n = grid.length;
        m = grid[0].length;

        grid[x0][y0] = 0; //当前元素设置为0，避免再次搜索到
        int[][] dir = {{0,1},{0,-1},{1,0},{-1,0}};
        //下、上、右、左
        for(int i=0; i<4; i++){
            int x = x0 + dir[i][0];
            int y = y0 + dir[i][1];
            if(x>=0&&x<n&&y>=0&&y<m&&grid[x][y]==1)
                sum+=dfs(grid, x, y);
        }
        return sum;
    }
    /**
     * bytedance 2.3. 搜索旋转排序数组
     */
    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) return -1;
        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < nums[right]) {
                if (nums[mid] < target && nums[right] >= target) left = mid + 1;
                else right = mid - 1;
            } else {
                if (nums[left] <= target && nums[mid] > target) right = mid - 1;
                else left = mid + 1;
            }
        }
        return -1;
    }
    public int search_self(int[] nums, int target) {
        int index=-1;
        int flag=0;
        for(int i=0;i<nums.length-1;i++){
            if(nums[i]>nums[i+1]){
                //左边二分
                if(target>nums[0]){
                    index=binarySearch(nums,0,i,target);
                }else if(target==nums[0]){
                    index=0;
                }else{
                    //右边二分
                    index=binarySearch(nums,i+1,nums.length-1,target);
                }
                flag=1;
                break;
            }
        }
        if(flag==0){
            index=binarySearch(nums,0,nums.length-1,target);
        }
        return index;
    }
    //二分查找
    int binarySearch(int [] nums,int start,int end,int target){
        int index=-1;
        if(start>end)
            return -1;
        else if(start==end){
            if(nums[start]==target)
                return start;
            else
                return -1;
        }else{
            int mid=start+(end-start)/2;
            if(nums[mid]==target){
                return mid;
            }else if(nums[mid]<target){
                index=binarySearch(nums,mid+1,end,target);
            }else{
                index=binarySearch(nums,start,mid,target);
            }
        }
        return index;
    }
    /**
     * bytedance 2.4. 最长连续递增序列
     */
    public int findLengthOfLCIS(int[] nums) {
        int max=1,len=1;
        if(nums.length==0)return 0;
        else if(nums.length==1)return 1;
        else{
            int i=0,j=i+1;
            while(j<nums.length){
                if(nums[i]<nums[j]){
                    max++;
                    if(len<max)
                        len=max;
                    i++;
                    j++;
                }else{
                    if(len<max)
                        len=max;
                    max=1;
                    i++;
                    j++;
                }
            }
        }
        return len;
    }
    /**
     * bytedance 2.5. 数组中的第K个最大元素
     */
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        int i=nums.length-1;
        int sum=1;
        while(i>=0){
            if(sum==k)
                return nums[i];
            else{
                i--;sum++;
            }
        }
        return 0;
    }
    /**
     * bytedance 2.6.最长连续序列
     */
    public int longestConsecutive(int[] nums) {
        Arrays.sort(nums);
        int max=1;
        if(nums.length==0)return 0;
        else if(nums.length==1)return 1;
        else{
            int i=0,j=1,len=1;
            while(j<nums.length){
                if(nums[j]==nums[i]+1){
                    len++;i++;j++;
                    if(max<len)max=len;
                }else if(nums[j]==nums[i]){
                    i++;j++;
                }else{
                    i++;j++;len=1;
                }
            }
        }
        return max;
    }
    /**
     * bytedance 2.7.第k个排列
     * https://blog.csdn.net/qq_38310176/article/details/81227086
     */
    public String getPermutation(int n, int k) {
        String result = "";
        java.util.Vector<Integer> v = new java.util.Vector<Integer>();
        for(int i=1;i<=n;i++) v.add(i);
        int num = 0, f = 0;
        for(int i=1;i<n;i++) {
            //开头固定了，去掉开头不是选中的那些数
            k -= (num-1)*f;
            f = Solution.Factorial(n-i);
            //num是获取的下标
            num = (int)Math.ceil((double)k/f);
            result += String.valueOf(v.get(num-1));
            v.remove(num-1);
        }
        return result+v.get(0);
    }
    //求阶乘
    public static int Factorial(int n) {
        while(n > 1) {
            return n*Factorial(n-1);
        }
        return 1;
    }
}
